LU 分解

阐述

LU 分解是将矩阵分解为一个下三角矩阵（对角元为 1）和一个上三角矩阵的乘积。

LU 分解可以通过 Gaussian 消去得到，其中 $L$ 记录了消去过程中的系数，而 $U$ 记录了消去的结果。

LU 分解可以应用于线性方程中，将 $Ax=b$ 转化为 $LUx=b$，然后通过两步来求解：

1. 求解 $Lc=b$（前代法）
2. 求解 $Ux=c$（回代法）

由于前代法和回代法计算简单（$O(n^2)$），基本上所有用到 $A^{-1}$ 的地方都可以用 $LU$ 代替。求解 $A^{-1}$ 不仅计算量大，还会产生误差和丢失稀疏性和其他结构。

LU 分解本身也可以用于矩阵求逆，只需要解 $LUX=I$ 这个方程就可以了，也就是求解 $n$ 个形如 $LUx_i=e_i$ 的方程。

部分 pivoting

计算 $PA=LU$

特殊情况

• 上三角、下三角矩阵：复杂度 $O(m^2)$
• 正定 Hermite 矩阵：通过 Cholesky 分解可以在 $m^3/3$ 步之内完成
• 三对角矩阵：复杂度 $O(m)$
• 带状矩阵，带宽 $b$：复杂度 $O(mb^2)$
• 稀疏矩阵

实例

性质

复杂度分析

• 消去过程：$2m^3/3+O(m^2)$
• 前代、回代过程：$2m^2+O(m)$

算法稳定性

直接分解是不稳定的，但部分 pivoting 是后向稳定的

在极少数情况下，后向误差的常数项可能会非常大，这时候适合使用 QR 分解。

相关内容

参考文献